#include "sd_blist.h"
#include "sd_memory.h"

static sd_BlistNode* CreateNode(sd_Blist* blist)
{
	sd_BlistNode* newnode;
	sd_MemoryAllocator* ma = blist->ma;
	SD_ASSERT(ma != NULL);
	newnode = (sd_BlistNode*)ma->allocate(sizeof(sd_BlistNode)+blist->node_cap*blist->elemsize-1);
	if (newnode == NULL)
	{
		SD_ASSERT(false);
		return NULL;
	}
	newnode->blist = blist;
	newnode->next = NULL;
	newnode->usedcount = 0;
	newnode->capacity = blist->node_cap;
	return newnode;
}

static sd_BlistNode* GetPredecessor(sd_Blist* blist, sd_BlistNode* node)
{
	sd_BlistNode* prenode;
	
	SD_ASSERT(node != NULL);
	
	/* If this node is the first node, so it has no predecessor */
	if (node == blist->firstNode)
		return NULL;

	prenode = blist->firstNode;
	while(prenode != NULL)
	{
		if (prenode->next == node)
			return prenode;
		prenode = prenode->next;
	}
	/* Not found */
	return NULL; 
}

static sd_Ret RemoveNode(sd_Blist* blist, sd_BlistNode* node)
{
	sd_MemoryAllocator* ma = blist->ma;
	SD_ASSERT(node != NULL && ma != NULL);
	if (node == blist->firstNode)
	{
		/* The blist must have at least 1 node */
		if (blist->lastNode == blist->firstNode)
		{
			blist->totalcount -= node->usedcount;
			node->usedcount -= node->usedcount;
		}
		else
		{
			blist->firstNode = node->next;
			blist->totalcount -= node->usedcount;
			ma->deallocate(node);
		}
	}
	else
	{
		sd_BlistNode* prenode = GetPredecessor(blist, node);
		SD_ASSERT(prenode != NULL);
		prenode->next = node->next;
		blist->totalcount -= node->usedcount;
		if (node == blist->lastNode)
			blist->lastNode = prenode;
		ma->deallocate(node);
	}
	return SD_RET_OK;
}


sd_Ret sd_BlistCreate(sd_Blist* blist, size_t elemsize, size_t node_cap, struct sd_MemoryAllocator* ma)
{
	blist->ma = ma;
	blist->elemsize = elemsize;
	blist->totalcount = 0;
	blist->node_cap = node_cap;
	if (blist->ma == NULL)
		blist->ma = sd_GetDefaultMemoryAllocator();
	/* Create the first node */
	blist->firstNode = CreateNode(blist); 
	blist->lastNode = blist->firstNode;
	return SD_RET_OK;
}

sd_Ret sd_BlistFree(sd_Blist* blist)
{
	sd_MemoryAllocator* ma = blist->ma;
	sd_BlistNode* node = blist->firstNode;
	sd_BlistNode* nextnode;
	while(node != NULL)
	{
		nextnode = node->next;
		ma->deallocate(node);
		node = nextnode;
	}
	return SD_RET_OK;
}

sd_Ret sd_BlistPushback(sd_Blist* blist, const void* elem)
{
	sd_BlistNode* lastNode = NULL;
	lastNode = blist->lastNode;
	size_t curcount = lastNode->usedcount;
	if (lastNode->usedcount == lastNode->capacity)
	{
		sd_BlistNode* newnode = CreateNode(blist);
		lastNode->next= newnode;
		blist->lastNode = newnode;
	}
	memcpy(&lastNode->buf[curcount*blist->elemsize], elem, blist->elemsize);
	/* Increase the counters */
	lastNode->usedcount++;
	blist->totalcount++;
	/* If the last node is full, create another node */
	if (lastNode->usedcount == lastNode->capacity)
	{
		sd_BlistNode* newnode = CreateNode(blist);
		lastNode->next= newnode;
		blist->lastNode = newnode;
	}
	return SD_RET_OK;
}
	
sd_Ret sd_BlistInsert(sd_Blist* blist, const void* elem)
{
	size_t curcount;
	sd_BlistNode* node = blist->firstNode;
	sd_BlistNode* lastNode = blist->lastNode;
	/* Find a unfull node */
	while(node->usedcount == node->capacity)
	{
		if (node->next == NULL)
		{
			sd_BlistNode* newnode = CreateNode(blist);
			lastNode->next= newnode;
			blist->lastNode = newnode;
		}
		node = node->next;
	}
	curcount = node->usedcount;
	memcpy(&node->buf[curcount*blist->elemsize], elem, blist->elemsize);
	node->usedcount++;
	blist->totalcount++;
	/* If the last node is full, create another node */
	if (node == lastNode && lastNode->usedcount == lastNode->capacity)
	{
		sd_BlistNode* newnode = CreateNode(blist);
		lastNode->next= newnode;
		blist->lastNode = newnode;
	}
	return SD_RET_OK;
}

sd_Ret sd_BlistInsertTogether(sd_Blist* blist, const void* elem1, size_t elem1size, const void* elem2)
{
	size_t curcount;
	sd_BlistNode* node = blist->firstNode;
	sd_BlistNode* lastNode = blist->lastNode;
	/* Find a unfull node */
	while(node->usedcount == node->capacity)
	{
		if (node->next == NULL)
		{
			sd_BlistNode* newnode = CreateNode(blist);
			lastNode->next= newnode;
			blist->lastNode = newnode;
		}
		node = node->next;
	}
	curcount = node->usedcount;
	memcpy(&node->buf[curcount*blist->elemsize], elem1, elem1size);
	memcpy(&node->buf[curcount*blist->elemsize+elem1size], elem2, blist->elemsize-elem1size);
	node->usedcount++;
	blist->totalcount++;
	/* If the last node is full, create another node */
	if (node == lastNode && lastNode->usedcount == lastNode->capacity)
	{
		sd_BlistNode* newnode = CreateNode(blist);
		lastNode->next= newnode;
		blist->lastNode = newnode;
	}
	return SD_RET_OK;
}

sd_Ret sd_BlistBegin(sd_Blist* blist, sd_BlistIterator* iter)
{
	iter->blist = blist;
	iter->curnode = blist->firstNode;
	iter->curindexInNode = -1;
	return SD_RET_OK;
}

sd_Ret sd_BlistNext(sd_BlistIterator* iter)
{
	if (iter->curindexInNode == -1)
		iter->curindexInNode = 0;
	else
		iter->curindexInNode++;
	while (iter->curindexInNode >= (int)iter->curnode->usedcount)
	{
		if (iter->curnode->next == NULL)
		{
			/* No more node to iterate*/
			return SD_RET_FALSE;
		}
		else
		{
			/* Jump to the next node */
			iter->curnode = iter->curnode->next;
			iter->curindexInNode = 0;
		}
	}
	return SD_RET_TRUE;
}


sd_Ret sd_BlistHasMore(sd_BlistIterator* iter)
{
	sd_BlistIterator oldIter = *iter;
	return sd_BlistNext(&oldIter);
}

sd_Ret sd_BlistGet(sd_BlistIterator* iter, void* elem)
{
	size_t elemsize = iter->blist->elemsize;	
	/* The user may not want to get the element' data when the 'elem' is NULL */
	if (elem != NULL)
	{
		int idx = iter->curindexInNode;
		sd_BlistNode* curnode = iter->curnode;
		memcpy(elem, &(curnode->buf[idx*elemsize]), elemsize);
	}
	return SD_RET_TRUE;
}

sd_Ret sd_BlistPartialGet(sd_BlistIterator* iter, void* key, int offset, size_t size)
{
	size_t elemsize = iter->blist->elemsize;		
	/* The user may not want to get the element' data when the 'elem' is NULL */
	if (key != NULL)
	{
		int idx = iter->curindexInNode;
		sd_BlistNode* curnode = iter->curnode;
		memcpy(key, &(curnode->buf[idx*elemsize+offset]), size);
	}
	return SD_RET_TRUE;
}

sd_Ret sd_BlistRemove(sd_BlistIterator* iter)
{
	sd_Ret ret;
	sd_BlistNode* curnode = iter->curnode;
	int idx = iter->curindexInNode;
	size_t movcount = (size_t)(curnode->usedcount - idx - 1);
	if (movcount > 0)
	{
		size_t elemsize = iter->blist->elemsize;
		memmove(&curnode->buf[idx*elemsize], &curnode->buf[(idx+1)*elemsize], movcount*elemsize);
	}
	curnode->usedcount--;
	iter->blist->totalcount--;
	if (curnode->usedcount == 0)
	{
		/* Remove the whole node */
		ret = RemoveNode(iter->blist, curnode);
		SD_ON_FAILED_RETURN(ret);
	}
	return SD_RET_OK;
}

sd_Ret sd_BlistClear(sd_Blist* blist)
{
	/* Only maintain the first node */
	sd_BlistNode* node = blist->firstNode->next;
	sd_BlistNode* tempNode;
	while(node != NULL)
	{
		tempNode = node;
		node = node->next;
		blist->ma->deallocate(tempNode);
	}
	blist->firstNode->usedcount = 0;
	blist->firstNode->next = NULL;
	blist->lastNode = blist->firstNode;
	blist->totalcount = 0;
	return SD_RET_OK;
}

sd_Ret sd_BlistUpdate(sd_BlistIterator* iter, const void* elem)
{
	size_t elemsize = iter->blist->elemsize;	
	/* The user may not want to get the element' data when the 'elem' is NULL */
	if (elem != NULL)
	{
		int idx = iter->curindexInNode;
		sd_BlistNode* curnode = iter->curnode;
		memcpy(&(curnode->buf[idx*elemsize]),elem , elemsize);
	}
	return SD_RET_TRUE;
}

sd_Ret sd_BlistUpdateTogether(sd_BlistIterator* iter, const void* elem1, size_t elem1size, const void* elem2)
{
	size_t elemsize = iter->blist->elemsize;	
	/* The user may not want to get the element' data when the 'elem' is NULL */
	if (elem1 != NULL)
	{
		int idx = iter->curindexInNode;
		sd_BlistNode* curnode = iter->curnode;
		memcpy(&(curnode->buf[idx*elemsize]),elem1 , elem1size);
		memcpy(&(curnode->buf[idx*elemsize+elem1size]),elem2 , elemsize-elem1size);
	}
	return SD_RET_TRUE;
}



